// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_STRING_HASHER_INL_H_
#define V8_STRING_HASHER_INL_H_

#include "src/string-hasher.h"

#include "src/char-predicates-inl.h"
#include "src/objects.h"
#include "src/objects/string-inl.h"
#include "src/utils-inl.h"

namespace v8 {
namespace internal {

    StringHasher::StringHasher(int length, uint64_t seed)
        : length_(length)
        , raw_running_hash_(static_cast<uint32_t>(seed))
        , array_index_(0)
        , is_array_index_(IsInRange(length, 1, String::kMaxArrayIndexSize))
    {
        DCHECK(FLAG_randomize_hashes || raw_running_hash_ == 0);
    }

    bool StringHasher::has_trivial_hash()
    {
        return length_ > String::kMaxHashCalcLength;
    }

    uint32_t StringHasher::AddCharacterCore(uint32_t running_hash, uint16_t c)
    {
        running_hash += c;
        running_hash += (running_hash << 10);
        running_hash ^= (running_hash >> 6);
        return running_hash;
    }

    uint32_t StringHasher::GetHashCore(uint32_t running_hash)
    {
        running_hash += (running_hash << 3);
        running_hash ^= (running_hash >> 11);
        running_hash += (running_hash << 15);
        int32_t hash = static_cast<int32_t>(running_hash & String::kHashBitMask);
        int32_t mask = (hash - 1) >> 31;
        return running_hash | (kZeroHash & mask);
    }

    template <typename Char>
    uint32_t StringHasher::ComputeRunningHash(uint32_t running_hash,
        const Char* chars, int length)
    {
        DCHECK_LE(0, length);
        DCHECK_IMPLIES(0 < length, chars != nullptr);
        const Char* end = &chars[length];
        while (chars != end) {
            running_hash = AddCharacterCore(running_hash, *chars++);
        }
        return running_hash;
    }

    void StringHasher::AddCharacter(uint16_t c)
    {
        // Use the Jenkins one-at-a-time hash function to update the hash
        // for the given character.
        raw_running_hash_ = AddCharacterCore(raw_running_hash_, c);
    }

    bool StringHasher::UpdateIndex(uint16_t c)
    {
        DCHECK(is_array_index_);
        if (!TryAddIndexChar(&array_index_, c)) {
            is_array_index_ = false;
            return false;
        }
        is_array_index_ = array_index_ != 0 || length_ == 1;
        return is_array_index_;
    }

    template <typename Char>
    inline void StringHasher::AddCharacters(const Char* chars, int length)
    {
        DCHECK(sizeof(Char) == 1 || sizeof(Char) == 2);
        int i = 0;
        if (is_array_index_) {
            for (; i < length; i++) {
                AddCharacter(chars[i]);
                if (!UpdateIndex(chars[i])) {
                    i++;
                    break;
                }
            }
        }
        raw_running_hash_ = ComputeRunningHash(raw_running_hash_, &chars[i], length - i);
    }

    template <typename schar>
    uint32_t StringHasher::HashSequentialString(const schar* chars, int length,
        uint64_t seed)
    {
#ifdef DEBUG
        StringHasher hasher(length, seed);
        if (!hasher.has_trivial_hash())
            hasher.AddCharacters(chars, length);
        uint32_t expected = hasher.GetHashField();
#endif

        // Check whether the string is a valid array index. In that case, compute the
        // array index hash. It'll fall through to compute a regular string hash from
        // the start if it turns out that the string isn't a valid array index.
        if (IsInRange(length, 1, String::kMaxArrayIndexSize)) {
            if (IsDecimalDigit(chars[0]) && (length == 1 || chars[0] != '0')) {
                uint32_t index = chars[0] - '0';
                int i = 1;
                do {
                    if (i == length) {
                        uint32_t result = MakeArrayIndexHash(index, length);
                        DCHECK_EQ(expected, result);
                        return result;
                    }
                } while (TryAddIndexChar(&index, chars[i++]));
            }
        } else if (length > String::kMaxHashCalcLength) {
            // String hash of a large string is simply the length.
            uint32_t result = (length << String::kHashShift) | String::kIsNotArrayIndexMask;
            DCHECK_EQ(result, expected);
            return result;
        }

        // Non-array-index hash.
        uint32_t hash = ComputeRunningHash(static_cast<uint32_t>(seed), chars, length);

        uint32_t result = (GetHashCore(hash) << String::kHashShift) | String::kIsNotArrayIndexMask;
        DCHECK_EQ(result, expected);
        return result;
    }

    IteratingStringHasher::IteratingStringHasher(int len, uint64_t seed)
        : StringHasher(len, seed)
    {
    }

    uint32_t IteratingStringHasher::Hash(String string, uint64_t seed)
    {
        IteratingStringHasher hasher(string->length(), seed);
        // Nothing to do.
        if (hasher.has_trivial_hash())
            return hasher.GetHashField();
        ConsString cons_string = String::VisitFlat(&hasher, string);
        if (cons_string.is_null())
            return hasher.GetHashField();
        hasher.VisitConsString(cons_string);
        return hasher.GetHashField();
    }

    void IteratingStringHasher::VisitOneByteString(const uint8_t* chars,
        int length)
    {
        AddCharacters(chars, length);
    }

    void IteratingStringHasher::VisitTwoByteString(const uint16_t* chars,
        int length)
    {
        AddCharacters(chars, length);
    }

    std::size_t SeededStringHasher::operator()(const char* name) const
    {
        return StringHasher::HashSequentialString(
            name, static_cast<int>(strlen(name)), hashseed_);
    }

} // namespace internal
} // namespace v8

#endif // V8_STRING_HASHER_INL_H_
